Thực đơn
Biến_đổi_Fourier_nhanh Các vấn đề tính toánVấn đề mở trong khoa học máy tính: Chặn dưới của độ phức tạp tính toán của biến đổi Fourier nhanh là gì? Liệu nó có thể nhanh hơn Θ(N log N) hay không? (các vấn đề mở khác trong khoa học máy tính) |
Một bài toán mở quan trọng về mặt lý thuyết là chứng minh chặn dưới cho độ phức tạp tính toán và số phép tính của biến đổi Fourier nhanh. Hiện vẫn chưa có chứng minh nào cho việc DFT có thực sự đòi hỏi Ω(N log N) phép tính, ngay cả trong trường hợp kích thước N là lũy thừa của hai, mặc dù không có thuật toán nào có độ phức tạp thấp hơn. Chú ý rằng tuy số phép tính thường là quan tâm chính về mặt lý thuyết, trên thực tế, tốc độ thực thi phụ thuộc nhiều yếu tố khác như các tối ưu hóa cho bộ nhớ đệm và ống lệnh CPU (CPU Pipes).
Theo công trình của Winograd năm 1978[3], chặn dưới chặt cho số phép nhân của FFT đã được biết là Θ(N).
Thực đơn
Biến_đổi_Fourier_nhanh Các vấn đề tính toánLiên quan
Biến Biến cố Phật giáo 1963 Biến đổi khí hậu Biến đổi khí hậu ở Việt Nam Biến đổi Z Biến thể Omicron SARS-CoV-2 Biến đổi tuyến tính Biến thể Beta SARS-CoV-2 Biến thể Alpha SARS-CoV-2 Biến đổi xã hộiTài liệu tham khảo
WikiPedia: Biến_đổi_Fourier_nhanh http://doi.acm.org/10.1145/1464291.1464352 //doi.org/10.1090%2FS0025-5718-1965-0178586-1 //doi.org/10.1090%2FS0025-5718-1978-0468306-4 //doi.org/10.1145%2F1464291.1464352 http://www.jstor.org/stable/2006266